#!/usr/bin/env python
# -*- coding: utf-8 -*-

# @Time     :2020/11/05
# @Author   :Changshu
# @File     :Exercise_414.py
# 414. 第三大的数
# 给定一个非空数组，返回此数组中第三大的数。如果不存在，则返回数组中最大的数。要求算法时间复杂度必须是O(n)。
import sys
def thirdMax(nums: list) -> int:
	if nums is None and len(nums)==0:
		return None
	if len(nums)<3:
		return max(nums)
	first,second,third=-sys.maxsize-1,-sys.maxsize-1,-sys.maxsize-1
	for n in nums:
		if n>first:
			third=second
			second=first
			first=n
		elif n<first:
			if n>second:
				third=second
				second=n
			elif n<second:
				if n>third:
					third=n
	if third!=-sys.maxsize-1:
		return third
	return first



if __name__ == '__main__':

	#nums=[2,2,3,1]	# 1
	#nums=[5,4,3,2]	# 2
	nums=[1,2,3,4,3,1,2]
	print(thirdMax(nums))
